#include <stdio.h>
#include <stdlib.h>
#include "search.h"

int bst_insert(bs_tree *bst, int data){
    if(*bst == NULL){
        bst_node *new = (bst_node *)malloc(sizeof(bst_node));
        if(new == NULL){
            perror("malloc");
            return -1;
        }

        new->data = data;
        new->lchild = new->rchild = NULL;
        *bst = new;
        return 0;
    }

    if((*bst)->data == data){
        printf("%d is already in the tree\n", data);
        return -1;
    }

    if(data < (*bst)->data){
        bst_insert(&((*bst)->lchild), data);
    }

    if(data > (*bst)->data){
        bst_insert(&((*bst)->rchild), data);
    }

    return 0;
}

bs_tree bst_create(int data[], int size){
    bs_tree bst = NULL;
    
    for(int i = 0; i < size; i++){
        bst_insert(&bst, data[i]);
    }

    return bst;
}

bst_node *bst_search(bs_tree bst, int data){
    if(bst == NULL){
        //printf("bstree is empty\n");
        return NULL;
    }

    if(bst->data == data){
        return bst;
    }

    if(bst->data < data){
        return bst_search(bst->rchild, data);
    }

    if(bst->data > data){
        return bst_search(bst->lchild, data);
    }

    return 0;
}

int bst_delete_node(bs_tree *bst, int data){
    if(*bst == NULL){
        printf("bstree empty or no %d in the bstree\n",data);
        return -1;
    }

    if(data < (*bst)->data)
        return bst_delete_node(&((*bst)->lchild), data);
    
    if(data > (*bst)->data)
        return bst_delete_node(&((*bst)->rchild), data);
    
    bst_node *tmp = *bst;
    if((*bst)->lchild == NULL){
        *bst = (*bst)->rchild;
        free(tmp);
    }
    else if((*bst)->rchild ==  NULL){
        *bst = (*bst)->lchild;
        free(tmp);
    } 
    else{
        bst_node *l_max = (*bst)->lchild;
        bst_node **l_max_parent = &((*bst)->lchild);
        while(l_max->rchild != NULL){
            l_max_parent = &(l_max->rchild);
            l_max = l_max->rchild;
        }

        (*bst)->data = l_max->data;
        *l_max_parent = l_max->lchild;
        free(l_max);
    }

    return 0;
}

void bst_free(bs_tree bst) {
    if (bst == NULL) return;
    bst_free(bst->lchild);
    bst_free(bst->rchild);
    free(bst);
}